#include<iostream>
#include<string>
using namespace std;


class ReversePairs{
	public:
		int merge(int arr[],int L,int R,int M){
			int *cp_arr = new int(arr[R-L+1]); 		
			int pl1 = L;
			int pl2 = M+1;
			int i = 0;
			int res = 0;
			while(pl1<=M && pl2<=R){
				if(arr[pl1]<=arr[pl2]){
					cp_arr[i] = arr[pl2];
					pl2++;
					i++;
				}
				else{
					res += (R - pl2 +1);
					cp_arr[i] = arr[pl1];
					pl1++;
					i++;
				}

			}
			while(pl1<=M){
				cp_arr[i] = arr[pl1];
				i++;
				pl1++;
			}
			while(pl2<=R){
				cp_arr[i] = arr[pl2];
				i++;
				pl2++;
			}
			return res;
		}
		int process(int arr[],int L,int R){
			if(L==R){
				return 0;
			}
			int M = L+((R-L)>>1);
			return process(arr,L,M)+process(arr,M+1,R)+merge(arr,L,R,M);
			
		}

};
void test(){
	ReversePairs t1;
	int arr[] = {7,1,1,6,1,1};
	cout<<"res = "<<t1.process(arr,0,5)<<endl;
}

int main(){
	test();

	return 0;
}
